package com.poxz.algorithm.template;

import java.util.Arrays;

/**
 * 数组操作
 *
 * @author poxz
 */
public class ArrayOps {

    /**
     * 前缀和
     *
     * @param a 原数组
     * @return 前缀和数组
     */
    static long[] prefixSum(int[] a) {
        int n = a.length;
        long[] s = new long[n + 1];
        for (int i = 0; i < n; i++) {
            s[i + 1] = s[i] + a[i];
        }
        return s;
    }

    /**
     * 差分数组
     *
     * @param a 原数组
     * @return 差分数组
     */
    static int[] difference(int[] a) {
        int n = a.length;
        int[] b = new int[n + 2];
        for (int i = 0; i < n; i++) {
            b[i] += a[i];
            b[i + 1] -= a[i];
        }
        return b;
    }

    /**
     * 二分：找第一个>=x的位置
     *
     * @param a 已排序数组
     * @param x 目标值
     * @return 第一个>=x的位置，不存在返回-1
     */
    static int lowerBound(int[] a, int x) {
        int l = 0, r = a.length - 1;
        while (l < r) {
            int mid = l + r >> 1;
            if (a[mid] >= x) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return a[l] >= x ? l : -1;
    }

    /**
     * 二分：找最后一个<=x的位置
     *
     * @param a 已排序数组
     * @param x 目标值
     * @return 最后一个<=x的位置，不存在返回-1
     */
    static int upperBound(int[] a, int x) {
        int l = 0, r = a.length - 1;
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if (a[mid] <= x) {
                l = mid;
            } else {
                r = mid - 1;
            }
        }
        return a[l] <= x ? l : -1;
    }

    /**
     * 离散化
     *
     * @param a 已排序数组
     * @param x 目标值
     * @return 目标值的索引
     */
    static int find(int[] a, int x) {
        return Arrays.binarySearch(a, x);
    }

    /**
     * 功能测试
     *
     * @param args 命令行参数
     */
    public static void main(String[] args) {
        System.out.println("=== 数组操作示例 ===\n");

        int[] arr = {1, 2, 3, 4, 5};
        long[] prefix = prefixSum(arr);
        System.out.println("原数组: " + Arrays.toString(arr));
        System.out.println("前缀和: " + Arrays.toString(prefix));
        System.out.println("区间[1,3]的和: " + (prefix[4] - prefix[1]));
        System.out.println();


        int[] a = {5, 2, 8, 1, 9};
        Arrays.sort(a);
        System.out.println("排序后: " + Arrays.toString(a));
        System.out.println();

        int pos = Arrays.binarySearch(a, 8);
        System.out.println("8 的位置: " + pos);
        System.out.println();

        int[] sorted = {1, 2, 4, 4, 5, 7};
        int idx = lowerBound(sorted, 4);
        System.out.println("第一个>=4的位置: " + idx);
        System.out.println();

        int[] fill = new int[5];
        Arrays.fill(fill, 999);
        System.out.println("填充后: " + Arrays.toString(fill));
        System.out.println();

        int[] copy = Arrays.copyOf(arr, arr.length);
        System.out.println("复制数组: " + Arrays.toString(copy));
        System.out.println();

        int[] range = Arrays.copyOfRange(arr, 1, 4);
        System.out.println("复制[1,4): " + Arrays.toString(range));
    }
}
